The present invention related to image compression, and in particular to variable length coding of a series of quantized transform coefficients of a block of image data.
Digital video compression ranges from coding still video/image to coding moving video for photographic, broadcasting, streaming, and conferencing applications. Modern transform based techniques include dividing an image into blocks, transforming the blocks of image data into transform coefficients, quantizing the coefficients, ordering the coefficients along a path, e.g., a zig-zag path on the two-dimensional transform domain, and encoding the series of quantized coefficients using a variable length coding method.
Two-dimensional variable length coding (2D-VLC) includes collecting or assuming the statistics of two dimensional block transform coefficient events that are each a run of the most-likely-to-occur amplitude, e.g., 0, followed by another amplitude. The coding includes assigning variable length codes, e.g., optimal codes such as Huffman codes or Arithmetic codes, to each event. In the description herein, 0 is assumed to be the most-likely-to-occur amplitude. The collecting or assuming statistics includes tracking the quantized non-zero-valued coefficient amplitudes and the number of zero-valued coefficients preceding the non-zero amplitude, i.e., tracking the runlengths of zeros which precedes any non-zero amplitude along a specified path, e.g., a zigzag scan path for a block of coefficients, e.g., an n by n coefficient block.
2D-VLC is used in common transform coding methods such as JPEG, MPEG1, MPEG2, ITU-T-261, etc., as follows. For motion video, an image is divided into blocks, e.g., 8 by 8 or 16 by 16 blocks. Each image is classified as interframe or intraframe. Interframe images are typically post motion compensation. The blocks of the image are transformed and the transform coefficients are quantized. The quantized transform coefficients are then coded along a specified path according to a 2D-VLC table. Interframe and intraframe images typically have different 2D-VLC tables. The DC component is typically separately encoded. Furthermore, the 2D-VLC table may be truncated so that the least frequently occurring events use an escape code followed by a fixed length code. A special “EOB” code is used to indicate the end of block when all remaining coefficients are zero.
For still images, all images are “intraframe” and a unique 2D-VLC table is exclusively designed to code the block based quantized coefficients.
In the latest coding developments, 2D-VLC has further been extended to multiple tables to adapt to video contents.
FIG. 1 shows how a table lookup may be used to implement a 2D-VLC scheme. Prior to the table look up, the runlength of zero amplitudes preceding any non-zero amplitude and the non-zero amplitude are determined. The table look up uses a 2D table for those likely events encoded using variable length encoding. An escape code together with a fixed length code is used for relatively less likely-to-occur combinations
The advantage of 2D_VLC is that both the position of each non-zero-valued coefficient as indicated by the runlength, and the quantized amplitude value are coded simultaneously as a pair using one 2D-VLC table. This may result in shorter codes, i.e., codes that use fewer bits than using separate VLC tables for each non-zero-valued coefficient and for its amplitude.
Because of the widespread use of image coding, many patents have been issued on different forms of VLC. U.S. Pat. No. 4,698,672 issued Oct. 6, 1987 to Wen-hsiung Chen, one of the inventors of the present invention, for example described one form of a two-dimensional variable length coding method.
Extensions and variations to the common 2D-VLC method are known. For example, the ITU H.263 compression standard defines one such variation sometimes called three-dimensional VLC (3D-VLC). See PCT patent publication WO 9318616 published Sep. 16, 1993 titled PICTURE DATA ENCODING METHOD and also the ITU-T H.263 standard. In 3D-VLC, each symbol (“event”) is a triplet (LAST, RUN, LEVEL) that includes: LAST, a binary flag that indicates whether or not the current non-zero amplitude-value is the last non-zero-valued coefficient in the block, RUN, the run-length of zero-value coefficients that precede the current non-zero amplitude, i.e., the number of zeroes since the last non-zero coefficient amplitude, and LEVEL, the current non-zero coefficient amplitude value. Thus, there is no need for a separate EOB codeword; whether or not the non-zero-valued coefficient is the last one is incorporated into the event.
FIG. 2 shows how a table lookup may be used to implement 3D-VLC.
One deficiency of 2-D VLC methods is that every non-zero-valued coefficient needs to be accompanied by one runlength to identify its position. In block based transform coding, it may occur that there are a number of consecutive non-zero-valued coefficients along the pre-determined coding path. This may especially occur in intraframe coding and high bit rate interframe coding, where there are likely to be clusters of consecutive non-zero-valued coefficients. The 2D-VLC method requires a separate runlength code, e.g., C10, C20, C30 . . . , etc., for each of the consecutive non-zero-valued coefficients. Thus there is a need in the art for a method that provides for efficiently encoding a sequence of consecutive non-zero coefficient values.
Furthermore, in low-bit rate interframe coding, there are likely to be mostly very-low amplitude coefficients, and these non-zero-valued coefficients are likely to be scattered. Furthermore, the clustered or scattered nature of the distribution is specifically dependent upon the block content itself regardless of still image where there are only “intraframe” blocks, or moving video where there are both interframe and intraframe blocks. The distribution of quantized coefficients along the path generally includes various clustered non-zero values in intraframe coding and high bit rate interframe coding and more scattered non-zero values in low bit rate interframe coding. It is thus rather inefficient to use only the same variable length coding technique to code the intraframe or interframe transform coefficients over and over again without worrying about the clustering or scattering of the coefficient distributions.
With these observations in mind, the above-mentioned Basic Hybrid VLC Method was developed that encodes position and amplitude of transform coefficients separately and takes advantage of the nature of the distribution of the transform coefficients in the low frequency and the high frequency regions. Furthermore, the above-mentioned Extended Hybrid VLC Method was invented for, and provides an alternative coding method for the high frequency region by taking advantage of the very few amplitude values in the high frequency region, especially, for example, for low bit rate and interframe applications.
In one embodiment of the Basic Hybrid VLC Method, two independent types of the coding schemes are introduced to code the quantized coefficients along the path. A boundary is established along the path to define two regions, e.g., a low frequency region and a high frequency region. The boundary can be made adaptive to the video depending on a number of factors such as intraframe coding or interframe coding, standard definition television (SDTV) or high definition television (HDTV), complex scene or simple scene, high bit rate coding or low bit rate coding, and so forth. In one embodiment, the encoding of the quantized coefficients in the low-frequency region includes coding the positions of consecutive non-zero-valued coefficients and the positions of consecutive zero-valued coefficients using a run-length coding method of a first type and a run-length coding method of a second type. The encoding further includes coding the amplitude values and sign of the non-zero-valued coefficients. In the high-frequency region, in one embodiment, the encoding of coefficients in the high frequency region includes encoding the positions of runs of none or more consecutive zero-valued coefficients using a run-length coding method of a third type. The encoding further includes coding the amplitude values and sign of the non-zero-valued coefficients.
In one embodiment of the Extended Hybrid VLC Method, a coding method is used in the second region that takes into account that almost all non-zero-valued coefficients in the high frequency region are ±1. No amplitude coding is needed to encode runs of consecutive zeroes that end a coefficient of amplitude 1. An exception (escape) code is included to encode those rare non-zero-valued coefficients that have values other than ±1.
Although the Basic Hybrid VLC Method and the Extended Hybrid VLC Method provide potential improvement beyond using a single 2D-VLC technique for all quantized coefficients in a block, these methods may not be optimal for various reasons, including that the dynamic nature of the quantized block coefficients may not exactly match the model assumed in a pre-determined coding techniques. By the dynamic nature we mean changed in block-to-block, and image to image in one or more of the cluster or scatter of the coefficients in a region, in whether a region has significant consecutive runs of non-zero-valued coefficients or mostly isolated non-zero-valued coefficients, in whether a region has coefficients with amplitudes dominated by a few values or even a single value, and so forth.
There is a need in the art for variable length coding methods applicable to quantized coefficients that include determining the nature of the coefficients themselves and using such determined nature information to select the coding method.
Furthermore, one or more patents describing some existing 2D-VLC coding methods have recently been the subject of patent litigation. Thus, there is a need in the art for alternate methods that can replace commonly used 2D-VLC methods that have been the subject of such litigation.